package leetcode.nowcoder链表分割;

import leetcode.ListNode;

public class Solution {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        //定义两个链表，一个放小于x的，一个放大于x的
        //要考虑两个链表最终可能为空的情况，所以需要引入哨兵结点
        ListNode last1=new ListNode(-1);//小于x链表的尾结点
        ListNode last2=new ListNode(-1);//大于x链表的尾结点

        ListNode head1=last1;
        ListNode head2=last2;

        for(ListNode cur=pHead;cur!=null;cur=cur.next) {
            if(cur.val<x) {
                last1.next=cur;
                last1=cur;
            }else {
                last2.next=cur;
                last2=cur;
            }
        }

        last1.next=head2.next;

        //最后，让last2.next置为空，避免造成循环链表    比如1  6  4   x=5
        last2.next=null;

        return head1.next;
    }
}
